# 图示例参考本目录下的: 示例.png图片
graph = {
    'A': ['C', 'E'],
    'B': ['F'],
    'C': ['B', 'D', 'F'],
    'D': ['F'],
    'E': ['F'],
    'F': [],  # 需要 防止KeyError
}

# 深度优先遍历 - 一路走到底直到走不通
def depth_first_search(graph, v):
    """
    graph: 用邻接表表示
    v: 为起始顶点

    思路:
        把起始顶点v加入到栈中
        如果栈不为空(循环)
            v出栈
            加入到已经访问集合中
            打印输出结果
            遍历与v相邻的所有节点w
                如果w还没有访问过且不在栈中
                加入到栈中
    """
    stack = []
    stack.append(v)
    visited = set()
    while stack:
        v = stack.pop()
        visited.add(v)
        print(v, end=' ')
        for w in graph[v]:
            if w not in visited and w not in stack:
                stack.append(w)

# A E F C D B 
depth_first_search(graph, 'A')